package com.platform.modules.alg.alglib.poj1741;


import java.util.Arrays;

public class Poj1741A {
    public String output = "";

    private int MX = 40005;
    private int MXE = 40005; // 加上虚拟节点，重建树共 2N个 节点，边数4N

    // 原图
    private Edge edge[] = new Edge[MXE];
    // 重构图
    private Edge E[] = new Edge[MXE];

    int Head[] = new int[MX];
    int head[] = new int[MX];
    int tail[] = new int[MX];
    int tot;
    int rear;
    int Max;
    int sz[] = new int[MX]; //子树大小
    int mark[] = new int[MX];//标记虚实节点
    int N, n, k, cnt, root, midedge;
    int ans;
    node T[] = new node[MX];
    // 保存左右子树中每个实节点到根的距离，len[]为数组下标
    int q[][] = new int[2][MX];
    int len[] = new int[2];


    public Poj1741A() {
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new Edge();
            E[i] = new Edge();
        }
        for (int i = 0; i < T.length; i++) {
            T[i] = new node();
        }
    }

    // 原图初始化
    void init() {
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }
        tot = 0;
    }

    // 重构图初始化
    void INIT() {
        for (int i = 0; i < Head.length; i++) {
            Head[i] = -1;
        }
        rear = 0; // 下标从零开始
    }

    // 原图加边
    void add(int u, int v, int w) {
        edge[tot].v = v;
        edge[tot].w = w;
        edge[tot].nxt = head[u];
        head[u] = tot++;
    }

    // 重构图加边
    void ADD(int u, int v, int w) {
        E[rear].v = v;
        E[rear].w = w;
        E[rear].nxt = Head[u];
        Head[u] = rear++;
    }

    // 删除 u 结点的 i 号边
    void Delete(int u, int i) {
        if (Head[u] == i)
            Head[u] = E[i].nxt;
        else
            E[E[i].pre].nxt = E[i].nxt; // 跳过该边
        if (tail[u] == i) // 指向 u 结点的最后一条边，相当于尾指针
            tail[u] = E[i].pre;
        else
            E[E[i].nxt].pre = E[i].pre; // 双向链表修改前驱
    }

    // 保证每个点的度不超过 2
    void build(int u, int fa) {
        int father = 0;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v, w = edge[i].w;
            if (v == fa) continue;
            if (father == 0) // 还没有增加子节点，直接连上
            {
                ADD(u, v, w);
                ADD(v, u, w);
                father = u;
            } else // 已经有一个子节点，则创建一个新节点，把v连在新节点上
            {
                mark[++N] = 0;
                ADD(N, father, 0);
                ADD(father, N, 0);
                father = N;
                ADD(v, father, w);
                ADD(father, v, w);
            }
            build(v, u);
        }
    }

    // nxt 是下一条边的编号，pre 是上一条边的编号
    void get_pre() // 得到每条边的前驱
    {
        for (int i = 0; i < tail.length; i++) {
            tail[i] = -1;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = Head[i]; j != -1; j = E[j].nxt) {
                E[j].pre = tail[i];
                tail[i] = j; // 指向 u 结点的最后一条边，相当于尾指针
            }
        }
    }

    // 重构图
    void rebuild() {
        // 重构图初始化
        INIT();
        N = n;
        for (int i = 1; i <= N; i++)
            mark[i] = 1;
        build(1, 0);
        get_pre(); // 得到每条边的前驱
    }

    // 创建距离树，入队，求新树每个子树大小
    void dfs_size(int u, int fa, int dir, int flag) {
        if (mark[u] != 0)
            q[flag][len[flag]++] = dir;//子树所有实节点到根的距离入队
        sz[u] = 1;
        for (int i = Head[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v, w = E[i].w;
            if (v == fa) continue;
            dfs_size(v, u, dir + w, flag);
            sz[u] += sz[v];
        }
    }

    // 找中心边
    void dfs_midedge(int u, int code) {
        if (Math.max(sz[u], sz[T[root].rt] - sz[u]) < Max) {
            Max = Math.max(sz[u], sz[T[root].rt] - sz[u]); // sz[T[root].rt]为该子树结点总数
            midedge = code;
        }
        for (int i = Head[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if (i != (code ^ 1))
                dfs_midedge(v, i);
        }
    }

    void solve(int ls, int rs, int midlen) {//查询距离不超过k的节点数
        Arrays.sort(q[0], 0, len[0]);
        Arrays.sort(q[1], 0, len[1]);
        for (int i = 0, j = len[1] - 1; i < len[0]; i++) {
            while (j >= 0 && q[0][i] + q[1][j] + midlen > k)
                j--;
            ans += j + 1;
        }
    }

    int getmide(int id, int u, int flag) { // 求解中心边
        Max = N;
        midedge = -1;
        root = id;
        T[id].rt = u;
        len[flag] = 0;
        dfs_size(u, 0, 0, flag);
        dfs_midedge(u, -1);
        return midedge;
    }

    void DFS(int id, int midedge, int flag) {//递归求解
        if (midedge != -1) {
            //中心边的左右2点
            int p1 = E[midedge].v;
            int p2 = E[midedge ^ 1].v;
            //中心边长度
            T[id].midlen = E[midedge].w;
            //左右子树
            T[id].ls = ++cnt;
            T[id].rs = ++cnt;
            //删除中心边
            Delete(p1, midedge ^ 1);
            Delete(p2, midedge);
            int t1 = getmide(T[id].ls, p1, 0);
            int t2 = getmide(T[id].rs, p2, 1);
            solve(T[id].ls, T[id].rs, T[id].midlen);
            DFS(T[id].ls, t1, 0);
            DFS(T[id].rs, t2, 1);
        }
    }

    public String cal(String input) {
        init();
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        k = Integer.parseInt(num[1]);
        for (int i = 1; i <= n - 1; i++) {
            String[] edge = line[i].split(" ");
            int u, v, w;
            u = Integer.parseInt(edge[0]);
            v = Integer.parseInt(edge[1]);
            w = Integer.parseInt(edge[2]);
            add(u, v, w);
            add(v, u, w);
        }
        ans = 0;
        if (n > 1) {
            rebuild(); // 重建
            root = 1;
            T[root].rt = 1; // T树根
            len[0] = 0; // 距离数组长度
            cnt = 1; // T树节点编号
            int t = getmide(1, 1, 0); // 得到中心边
            DFS(1, t, 0); // 边分治递归
        }
        output += ans + "";
        return output;
    }
}


class Edge {
    int v, w, nxt, pre;
}

class node {
    int rt; // 根节点编号
    int midlen; // 中心边的权值
    int ls, rs; // 左右子树编号
}
